// class Node{
//     data = null
//     left = null
//     right = null
//     parent = null
//     constructor(data){
//         this.data = data
//     }
// }

// class Tree{
//     root = null
//     // 插入元素
//     insert(tree,value){
//         const node = new Node(value)
//         if(tree.root === null){
//              // 插入第一个节点
//             tree.root = node
//             return
//         }
//         let tmp = tree.root
//         let parent = null
//         let flag = false
//         while(tmp !== null){
//             parent = tmp
//             flag = value < tmp.data
//             if(flag){
//                 tmp = tmp.left
//             }else{
//                 tmp = tmp.right
//             }
//         }
//         if(flag){
//             parent.left = node
//         }else{
//             parent.right = node
//         }
//         node.parent = parent
//         this.rebuild(parent,value)
//     }
//     rebuild(current,value){
//         let node = current
//         if(node === null){return}
//         while(node){
//             const bfValue = this.getHeight(node.left) - this.getHeight(node.right)
//             // 如果大于2，之前就应该调整了，所以不会大于2
//             if(bfValue === 2){
//                 const left = node.left
//                 if(left && left.right && left.right.data <= value){
//                     // 左右情况，先左旋
//                     this.leftRotate(left)
//                 }
//                 // 右旋
//                 this.rightRotate(node)
//             }else if(bfValue === -2){
//                 const right = node.right
//                 if(right && right.left && right.left.data >= value){
//                     // 右左情况，先左旋
//                     this.rightRotate(right)
//                 }
//                 // 左旋
//                 this.leftRotate(node)
//             }
//             node = node.parent
//         }
//     }
//     rightRotate(current){
//         if(current === null){return}
//         const {left} = current
//         const leftRight = left.right
//         current.left = leftRight
//         if(leftRight !== null){
//             leftRight.parent = current
//         }
//         left.parent = current.parent
//         if(left.parent){
//             if(left.parent.left === current){
//                 left.parent.left = left
//             }else{
//                 left.parent.right = left
//             }
//         }else{
//             this.root = left
//         }
//         current.parent = left
//         left.right = current
//     }
//     leftRotate(current){
//         if(current === null){return}
//         const {right} = current
//         const rightLeft = right.left
//         current.right = rightLeft
//         if(rightLeft !== null){
//             rightLeft.parent = current
//         }
//         right.parent = current.parent
//         if(right.parent){
//             if(right.parent.left === current){
//                 right.parent.left = right
//             }else{
//                 right.parent.right = right
//             }
//         }else{
//             this.root = right
//         }
//         current.parent = right
//         right.left = current
//     }

//     // 高度
//     getHeight(node=this.root){
//         if(node === null){return 0}
//         let leftHeight =  this.getHeight(node.left)
//         let rightHeigh = this.getHeight(node.right)
//         return Math.max(leftHeight,rightHeigh) + 1
//     }
//     // 普通树求最大值
//     getMax(node=this.root){
//         // 当前不支持负数
//         if(node === null){return -1}
//         let leftMax = this.getMax(node.left)
//         let rightMax = this.getMax(node.right)
//         let current = node.data
//         return Math.max(leftMax,rightMax,current)
//     }
//     find(value,node=this.root){
//         let current = node
//         while(current){
//             if(current.data === value){
//                 return current
//             }
//             if(current.data > value){
//                 current = current.left
//             }else{
//                 current = current.right
//             }
//         }
//         return null
//     }
//     del(value,tree=this){
//         if(tree === null || tree.root === null) {return false}
//         // 1.删除根节点，没有左右子树
//         const root = tree.root
//         if(root.data === value && root.left === null && root.right === null){
//             tree.root = null
//             return true
//         }
//         let current = tree.root
//         let parent = null
//         let position = 'right'
//         while(current){
//             const data = current.data
//             if(value === data) break
//             parent = current
//             if(data < value){
//                 current = current.right
//                 position = 'right'
//             }else{
//                 current = current.left
//                 position = 'left'
//             }
//         }
//         // 没找到
//         if(!current){return false}
//         // 2.叶子节点
//         if(current.right === null && current.left === null){
//             parent[position] = null
//             return true
//         }
//         // 3.只有左/右子树
//         if(!current.right || !current.left){
//             if(current.left){
//                 parent[position] = current.left
//             }else{
//                 parent[position] = current.right
//             }
//             return true
//         }
//         // 4.左右子树都不为空，右子树最大元素替代当前元素
//         let temp = current.left
//         let childParent = current
//         let childPosition = 'left'
//         while(temp.right){
//             childParent = temp
//             temp = temp.right
//             childPosition = 'right'
//         }
//         current.data = temp.data
//         childParent[childPosition] =  temp.left
//         return true
//     }
// }
// let  arrs = [6]
// arrs = [2,3,8,6,5,1,20]
// arrs = [2,3,8,6,5,1,20,12]
// arrs = [2,3,8,6,5,1,20,12,14]
// arrs = [2,3,8,6,5,1,20,12,14,16]
// arrs = [2,3,8,6,5,1,20,12,14,16,17]
// arrs = [2,3,8,6,5,1,20,12,14,16,17,19,11,10,9,8,7,4]
// const tree = new Tree()
// for (let i = 0; i < arrs.length; i++) {
//     tree.insert(tree,arrs[i])
// }

// function postorder(node,char){
//     if(node === null) return
//     postorder(node.left,char+'   ')
//     console.log(char,node.data)
//     postorder(node.right,char+'   ')
// }
// function print(){
//     postorder(tree.root,'')
//     console.log('--------------------------')
// }
// print()
// console.log(tree.getHeight(),tree.getMax(),tree.find(1))
// console.log(tree.del(6))
// console.log(tree.getHeight())
// const n1 = new Node(5)
// const n2 = new Node(4)
// const n3 = new Node(3)
// const n4 = new Node(2)
// const n5 = new Node(1)

// n1.left = n2
// n1.right = n3
// n2.left = n4
// n2.right = n5

// class Node{
//     data = null
//     left = null
//     right = null
//     constructor(data){
//         this.data = data
//     }
// }
// function createHuffman(arrs){
//     arrs.sort((a,b)=>a-b)
//     arrs = arrs.map(val => new Node(val))
//     while(arrs.length > 1){
//         let [left,right] = arrs
//         const parentValue = left.data + right.data
//         const parent = new Node(parentValue)
//         parent.left = left
//         parent.right = right
//         arrs = arrs.slice(2)
//         arrs.push(parent)
//         arrs.sort((n1,n2)=>n1.data-n2.data)
//     }
//     return arrs[0]
// }

// const tree = createHuffman([1,7,5,50,12])
// console.log(tree)